#include<cstdlib>

void sort(int* m, int size);

int main()
{
	const int s = 9;
	int mas[s] = { 5,8,62,0,5,9,7,0,1 };
	sort(mas, s);


	return 0;
}

void sort(int* m, int size)
{
	if (size > 1) {
		int i1 = 0;
		int i2 = size/2;
		int* m1 = (int*)malloc(sizeof(int)*i2);
		int* m2 = (int*)malloc(sizeof(int)*(size-i2));
		if (i2 > 1)
			sort(m, i2);
		if (size-i2 > 1)
			sort(m+i2, size-i2);

		for (int i = 0; i < i2; i++)
			m1[i] = m[i];
		for (int i = i2; i < size; i++)
			m2[i - i2] = m[i];

		int l = 0;
		int n = 0;
		for (int i = 0; i < size; i++) {
			if (l >= i2) {
				m[i] = m2[n];
				n++;
			}
			else if (n >= size - i2) {
				m[i] = m1[l];
				l++;
			}
			else if (m1[l] > m2[n]) {
				m[i] = m2[n];
				n++;
			}
			else {
				m[i] = m1[l];
					l++;
			}
		}
		free(m1);
		free(m2);
	}
}